// Package day_04_tree postorder_range
// @Title day_04_tree
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/8/30 16:53
// @Create  2021/8/30 16:53
package day_04_tree

// PostorderTraversal 使用递归实现  后序遍历一颗二叉树
func PostorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := make([]int, 0)
	var process = func(root *TreeNode) {}
	process = func(root *TreeNode) {
		if root == nil {
			return
		}
		process(root.Left)
		process(root.Right)
		ans = append(ans, root.Val)
	}
	process(root)
	return ans
}

// PostorderTraversalStack 使用两个栈实现后序遍历
func PostorderTraversalStack(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := make([]int, 0)
	// 准备两个栈
	stack1 := make([]*TreeNode, 0)
	stack2 := make([]*TreeNode, 0)
	stack1 = append(stack1, root)
	for len(stack1) > 0 {
		root = stack1[len(stack1)-1]
		stack1 = stack1[:len(stack1)-1]
		stack2 = append(stack2, root)
		if root.Left != nil {
			stack1 = append(stack1, root.Left)
		}
		if root.Right != nil {
			stack1 = append(stack1, root.Right)
		}
	}
	for len(stack2) > 0 {
		temp := stack2[len(stack2)-1]
		ans = append(ans, temp.Val)
		stack2 = stack2[:len(stack2)-1]
	}
	return ans
}
